package com.github.hgkmail.hello.leetcode101.design;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

//基础实现：哈希表HashMap（用于查找）+ 双向链表（记录新旧顺序 用于淘汰 不能用LinkedList因为其节点Node是私有类）
//快速实现：继承自LinkedHashMap，重写removeEldestEntry()方法（不符合考察要求）
//这种题的解法一般是组合多个基础数据结构（一般是2个）
public class LC146LRUCache {

    public static class LRUCache {
        //双向链表节点
        class LinkedListNode {
            int key;
            int value;
            LinkedListNode prev;
            LinkedListNode next;

            public LinkedListNode() { }

            public LinkedListNode(int k, int v) {
                key = k;
                value = v;
            }
        }

        //容量
        int capacity;
        //用于查找
        Map<Integer, LinkedListNode> find;
        //双向链表头和尾，使用[伪节点]，插入和删除操作比较统一，不用区分中间节点和头尾
        //dummy 假的，伪造的
        LinkedListNode dummyHead, dummyTail;

        public LRUCache(int cap) {
            capacity = cap;
            find = new HashMap<>();
            // 使用伪头部和伪尾部节点，这样插入、删除时不用区分中间节点和头尾
            dummyHead =new LinkedListNode();
            dummyTail =new LinkedListNode();
            dummyHead.prev=null;
            dummyHead.next= dummyTail;
            dummyTail.prev= dummyHead;
            dummyTail.next=null;
        }

        public int get(int key) {
            if (find.containsKey(key)) {
                LinkedListNode node = find.get(key);
                //断开节点
                removeNode(node);
                //移到开头
                insertToHead(node);

                return node.value;
            }
            return -1;
        }

        public void put(int key, int value) {
            if (find.containsKey(key)) {
                LinkedListNode exist = find.get(key);
                exist.value=value;
                //断开节点
                removeNode(exist);
                //移到开头
                insertToHead(exist);
                return;
            }
            LinkedListNode freshNode = new LinkedListNode(key, value);
            find.put(key, freshNode);
            //新节点放到开头
            insertToHead(freshNode);
            //检查是否超出容量capacity
            if (find.size()>capacity) {
                LinkedListNode oldestNode = dummyTail.prev;
                removeNode(oldestNode);
                find.remove(oldestNode.key);
            }
        }

        public void insertToHead(LinkedListNode node) {
            if (dummyHead.next==node) {
                return;
            }
            node.next= dummyHead.next;
            node.prev= dummyHead;
            dummyHead.next.prev=node;
            dummyHead.next=node;
        }

        public void removeNode(LinkedListNode node) {
            node.prev.next=node.next;
            node.next.prev=node.prev;
        }

        @Override
        public String toString() {
            StringBuilder sb=new StringBuilder();
            LinkedListNode curr = dummyHead.next;
            while (curr!= dummyTail) {
                sb.append(String.format("(%d,%d) ", curr.key, curr.value));
                curr=curr.next;
            }
            return sb.toString();
        }
    }

    //LinkedHashMap=hashmap+双向链表，支持insertion order和access order
    public static class LRUCache2 extends LinkedHashMap<Integer, Integer> {
        private final int capacity;

        public LRUCache2(int capacity) {
            //accessOrder=true
            super(capacity, .75f, true);
            this.capacity=capacity;
        }

        public int get(int key) {
            return super.getOrDefault(key, -1);
        }

        public void put(int key, int value) {
            super.put(key, value);
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity;
        }
    }

    public static void main(String[] args) {
        LRUCache lRUCache = new LC146LRUCache.LRUCache(2);
        lRUCache.put(2, 1);
        lRUCache.put(1, 1);
        lRUCache.put(2, 3);
        lRUCache.put(4, 1);
        lRUCache.get(1);
        lRUCache.get(2);
        System.out.println(lRUCache);
    }
}
